package com.faiz.algorithm;


import sun.security.util.Length;

import java.util.*;

public class Dijkstra {
    private static final int LEN = 6;
    private static int[][] matrix = {
            {0, 7, 12, 100, 100, 100},
            {100, 0, 2, 9, 100, 100},
            {100, 100, 0, 100, 10, 100},
            {100, 100, 100, 0, 100, 1},
            {100, 100, 100, 4, 0, 5},
            {100, 100, 100, 100, 100, 0}
    };
    //存储当前能到达的点和距离
    private static int[] reach = new int[LEN];
    //存储可到达的每个点的最短距离
    private static Map<Integer, Integer> dic = new HashMap<>();

    public static void dijkstra() {
        Arrays.fill(reach, 100);
        //首先将A能到达的点加入到reach中,初始化
        for (int j = 1; j < LEN; j++) {
            if (matrix[0][j] != 100 || matrix[0][j] != 0) {
                reach[j] = matrix[0][j];
            }
        }
        while (dic.size() < LEN - 1) {
            int point = getNearestIndex();
            for (int j = 1; j < LEN; j++) {
                if (point == j) {
                    continue;
                }
                if (reach[point] + matrix[point][j] < reach[j]) {
                    reach[j] = reach[point] + matrix[point][j];
                }
            }
        }
    }

    //返回当前reach中最小的值的点(index)
    public static int getNearestIndex() {
        int index = 0;
        int tmp = 100;
        for (int i = 0; i < LEN; i++) {
            if (reach[i] < tmp) {
                //需要排除已经确认的点
                if (dic.containsKey(i)) {
                    continue;
                }
                tmp = reach[i];
                index = i;
            }
        }
        dic.put(index, reach[index]);
        return index;
    }

    public static void main(String[] args) {
//        System.out.println("hello xixi");
        List<Integer>[] adjs = new List[5];
        adjs[1] = new ArrayList<>();
        adjs[1].add(1);
        System.out.println(adjs[1]);
//        dijkstra();
//        System.out.println(dic);
    }


}